import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
 class BinaySearch {
    public static int rank(int k,int[] array){
        return rank(k,array,0,array.length-1);

    }
    public static int rank(int k,int[] array,int left,int right,int depth){
        for(int i = 0;i<depth;i++){
            System.out.printf(" ");
        }
        System.out.println("left="+left+",right="+right);
        if(left>right) return -1;
        int mid = left+(right-left)/2;
        if(k<array[mid]) return rank(k,array,left,mid-1,depth+1);
        else if (k>array[mid]) return rank(k,array,mid+1, right,depth+1);
        else return mid;

    }
    public static int rank(int k,int[] array,int left,int right){
        if(left>right) return -1;
        int mid = left+(right-left)/2;
        if(k<array[mid]) return rank(k,array,left,mid-1);
        else if (k>array[mid]) return rank(k,array,mid+1, right);
        else return mid;

    }
    //+  -> 不在白名单上的值
    //-  -> 在白名单上的值
    public static void textdiffer(){
        int[] array = new int[]{5,2,6,11,8,9,1,0,3,4,7,22,99};//白名单
        int[] arr = new int[]{6,2,1,9,0,45,67,22,99,3,7,11,77,21};
        Scanner scanner = new Scanner(System.in);
        System.out.println("+ OR -");
        String arg = scanner.nextLine();
        Arrays.sort(array);
        for(int i = 0;i<arr.length;i++){
            if(arg.equals("-")&&rank(arr[i],array)!=-1){
                System.out.print(arr[i]+" ");
            }else if(arg.equals("+")&&rank(arr[i],array)==-1){
                System.out.print(arr[i]+" ");
            }
        }

    }
    //删除白名单上重复的值
    public static int[] textdiv(int[] array){
        Arrays.sort(array);
        List<Integer> list = new ArrayList<>();

        for(int i = 0;i< array.length-1;i++){
            if(array[i]!=array[i+1]){
                list.add(array[i]);
            }
        }
        //如果最后两个是相同的，那么前面那个在for循环中就不会添加入list中
        //如果最后两个不相同，那么在for循环的最后一次前面的那个就会加入到list中，后面的那个就会在接下来加入list中
        list.add(array[array.length-1]);

        array = new int[list.size()];
        for(int i = 0;i<array.length;i++){
            array[i] = list.get(i);
        }
        return array;
    }
    //等值键
    public static int rank(int[] array,int target){
        int left = 0;
        int right = array.length-1;
        int mid = -1;
        while(left<=right){
            mid = left+(right-left)/2;
            if(array[mid]<target){
                left = mid+1;
            }else if(array[mid]>target){
                right = mid-1;
            }else if(array[mid]==target){
                while(mid>=0&&array[mid]==target){
                    mid--;
                }
                return ++mid;
            }
        }
        return -1;
    }
    public static int count(int[] array,int key){
        int pos = rank(array,key);
        int num = pos != -1 ? 1 : 0;
        while(pos<=array.length-1&&array[pos+1]==key){
            num++;
        }
        return num;
    }

    public static void main(String[] args) {
        int[] a = new int[] {84, 48, 68, 10, 18, 98, 12, 23, 54, 57, 33, 16, 77, 11, 29, 11, 29, 77, 77};
        Arrays.sort(a);
        System.out.println(rank(a, 29));
        System.out.println(count(a,48));
    }

}
 class Gcd {
    public static int gcd(int p,int q){
        if(p<q){
            int tem = p;
            p = q;
            q = tem;
        }
        return gcd(p,q,0);
    }
    public static int gcd(int p,int q,int depth){
        if(q==0) return p;
        for(int i = 0;i<depth;i++){
            System.out.print(" ");
        }
        System.out.println("p = "+p+" q = "+q);
        int r = p % q;
        return gcd(q,r,depth+1);
    }
}
public class TextDemo{
     public static void text(Boolean[][] array,int i,int j){
         if(i!=j){
             array[i][j] = true;
         }else{
             array[i][j] = true;
         }


     }
    public static void main(String[] args) {

    }
}
